/*
 * CopyRight(C) Kenbin
 */

#ifndef LWS_CTRIEDICT_INCLUDED
#define LWS_CTRIEDICT_INCLUDED

#include <string>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

/*Comment#
   双数组Trie树

   1、Trie树

   Trie树是搜索树的一种

   [a|b|c|d| ... |g| ... |t| ... ]
      |           \
   [ |l|...|u| ] [ |e|...|o| ]
      |     |       \
    blue   but   [ |m|...|t| ]
                    |     |
                   gem   get

   2、双数组Trie树

   Trie树的空间复杂度为O(n),它的缺点是:数据结构复杂,查询效率低.

   为了让Trie树实用的算法在空间占用较少的同时保证查询的效率,Aoe,J提出了用两个线性
   数组来表示Trie树,即双数组Trie树.

   双数组Trie树本质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态,
   根据输入变量的不同进行状态的转移,当到达结束状态或者无法转移的时候,完成查询.

       c
   (s)--->(t)

   两个线性数组分别是base[]和check[],对于从状态s到状态t的一个转移,需要满足:

   check[base[s]+c] = s
   base[s]+c = t
   其中c是输入变量.

    base           check
   ------          ------
   |    |          |    |
   ------          ------
   |    |          |    |
   ------          ------
  s| t-c|          |    |
   ------          ------
   |    |          |    |
   ------          ------
   |    |          |    |
   ------          ------
   |    |         t|  s |
   ------          ------

   3、构造双数组Trie树

   把6768个GB2312常用汉字根据其内码(0-6767)依次从1-6768编号,这些汉字占用base数组
   的前6768个位置:base[1]-base[6768],其余的字符则占用base[6769]-base[N-6768](N为
   所有原子字符的数量,包括汉字、ascii字符、特殊符号等).

   如果base[s]=0,check[s]=-1,表示s位置为空.如果base[s]<0,表示s位置是一个词语.

   如何确定base[s]的值呢?

   对于每一个原子字符s,要确定其base值,则要保证字串sc1,sc2,..,scn都有空闲的位置可以
   占用,这些字串是以s字符开头的,可能是一个两字的词语,也可能是长词的前缀,需要满足如
   下等式:

   b = base[s]
   base[b+c1]  = base[b+c2]  = .. = base[b+cn]  = 0
   check[b+c1] = check[b+c2] = .. = check[b+cn] = -1

   确定了base[s]的值之后,同时也就确定了check数组中相应位置的值:
   check[b+c1] = check[b+c2] = .. = check[b+cn] = s

   依次类推,对于字串sc1(占用了base[b+c1]),要确定其base值,则要保证字串sc1m1,sc1m2,
   ..,sc1mn都有空闲的位置可以占用,这些字串是以sc1字串开头的,可能是一个三字的词语,
   也可能是长词的前缀,需要满足如下等式:

   k = base[b+c1]
   base[k+m1]  = base[k+m2]  = .. = base[k+mn]  = 0
   check[k+m1] = check[k+m2] = .. = check[k+mn] = -1

   确定了base[b+c1]的值之后,同时也就确定了check数组中相应位置的值:
   check[k+m1] = check[k+m2] = .. = check[k+mn] = b+c1

   依次类推,直到处理完所有词语.

   做完上面的处理,最后再遍历一次base数组,把那些被词语(不是前缀)占用的位置的值求负
   ,以指代其为词语.

   在构造好的双数组Trie树中查词过程如下:

   s = c
   t = abs(base[s]) + (++c)
   while check(t) == s:
     if base(t) < 0 then
       found one word
     s = t
     t = abs(base[s]) + (++c)

   4、扩展双数组Trie树

   procedure relocate{ s:state; b:base_index }
   {move base for state s to a new place beginning at b}
   begin
      for each input character c for the state s
      {i.e. for each c such that check[base[s]+c] = s}
      begin
         check[b+c] = s;{mark owner}
	 base[b+c] = base[base[s]+c];{copy data}
         {the node base[s]+c is to be moved to b+c;Hence, 
	 for any i for which check[i] = base[s]+c, update check[i] to b+c}
	 for each input character d for the node base[s]+c
	 begin
	    check[base[base[s]+c]+d] = b+c
	 end
	 check[base[s]+c] = none {free the cell}
      end
      base[s] = b
   end

*/

namespace LWS {

    class CTrainWord
    {
	public:
	    CTrainWord();

	    void Train(const char *corpus_file);
	    void QuickTrain(const char *word_file, const char *corpus_file);
	    void Output(const char *word_file);

	private:
	    map<string,int> m_word_freq;
    };

    class CMakeDict
    {
	public:
	    CMakeDict();

	    void Make(const char *word_file, const char *hazi_file);
	    void Output(const char *trie_txtfile, const char *trie_binfile);
	    void OutputCHAR(const char *CHAR_file);

	private:
	    struct Word
	    {
		int word_id;
		int word_freq;
		string word;
	    };

	    /* Double Trie Array Node, the first Node is Special */
	    struct TrieNode
	    {
		int base;
		int check;
		int word_id;
		int word_freq;
		string prefix;
		TrieNode() : 
		    base(0), 
		    check(-1), 
		    word_id(-1), 
		    word_freq(0), 
		    prefix("")
		{}
	    };

	    int calc_base(set<string> &fellow_CHARs);
	    int CHAR_index(string &CHAR);

	    int m_total_word_freq;

	    vector<Word> m_words;
	    string m_GB2312Hanzis[6768];
	    map<string, int> m_CHARs;
	    vector<TrieNode> m_trienodes;
    };

    struct TrieNode
    {
	int base;
	int check;
	int word_id;
	int word_freq;
	TrieNode() :
	    base(0), 
	    check(-1), 
	    word_id(-1), 
	    word_freq(0) 
	{}
    };

    class CTrieDict
    {
	public:
	    CTrieDict();
	    ~CTrieDict();

	    bool Load(const char *trie_binfile, const char *CHAR_file);

	    int Base(int trie_idx);
	    int Check(int trie_idx);
	    int WordId(int trie_idx);
	    float WordProb(int trie_idx);

	    int CHARIndex(string &CHAR);

	private:

	    int m_total_trienode;
	    int m_total_word;
	    int m_total_word_freq;

	    map<string, int> m_CHARs;
	    TrieNode *m_trienodes; 

	    friend class CExpanDict;
    };

    class CExpanDict
    {
	public:
	    CExpanDict(CTrieDict *dict);

	    void Expand(const char *new_word_file);
	    void Output(const char *new_trie_binfile);

	private:
	    int calc_base(set<int> &fellows);

	    CTrieDict *m_dict;
	    map<string, int> m_new_words;
    };

};

#endif
